% !Mode:: "TeX:UTF-8"
% !TeX root = ../rslbook.tex

\zhead{Переписать алгоритмы на RSL\footnote{задачи взяты из~\cite{Cormen}}}

\z Нахождение минимального элемента
\begin{codebox}
\Procname{$\proc{Minimum}(A)$}
\li $\id{min} \gets A[1]$
\li \For $i \gets 2$ \To $\id{length}[A]$
\li \Do \If $\id{min} > A[i]$
\li \Then $\id{min} \gets A[i]$ \End \End
\li \Return $\id{min}$
\end{codebox}

\z Сортировка методом вставок
\begin{codebox}
\Procname{$\proc{Sort}(A)$}
\li \For $j \gets 2$ \To $\id{length}[A]$
\li \Do $\id{key} \gets A[j]$
\li $i \gets j-1$
\li \While $i > 0$ and $A[i] > \id{key}$
\li \Do $A[i+1] \gets A[i]$
\li $i \gets i-1$ \End
\li $A[i+1] \gets \id{key}$ \End
\end{codebox}

\z Быстрая сортировка Хоара
\begin{codebox}
\Procname{$\proc{Quicksort}(A, p, r)$}
\li \If $p < r$
\li \Then $q \gets \proc{Partition}(A, p, r)$
\li $\proc{Quicksort}(A, p, q)$
\li $\proc{Quicksort}(A, q+1, r)$ \End
\end{codebox}

\begin{codebox}
\Procname{$\proc{Partition}(A, p, r)$}
\li $x \gets A[p]$
\li $i \gets p-1$
\li $j \gets r+1$
\li \While $\const{TRUE}$
\li \Do \Repeat $j \gets j-1$
\li \Until $A[j] \leqslant x$
\li \Repeat $i \gets i+1$
\li \Until $A[i] \geqslant x$
\li \If $i < j$
\li \Then $\mbox{поменять~} A[i] \leftrightarrow A[j]$
\li \Else \Return $j$ \End \End
\end{codebox}

\z Использовать следующее представление закрытых хеш-таблиц:
\begin{lstlisting}
type Key,
  ClosedHashElement == empty | occupied(elem:Key),
  ClosedHash = ClosedHashElement-list
\end{lstlisting}

\begin{codebox}
\Procname{$\proc{Hash-Insert}(T,k)$}
\li $i \gets 0$
\li \Repeat $j \gets h(k,i)$
\li \If $T[j] = \const{NIL}$
\li \Then $T[j] \gets k$
\li \Return $j$
\li \Else $i \gets i+1$ \End
\li \Until $i = m$ \End
\li \Error <<переполнение хеш-таблицы>>
\end{codebox}

\textbf{Решение:}
\begin{lstlisting}
variable T: ClosedHash
value m : Nat
value
  h: Key >< Nat -~-> Nat,
  insert: Key -~-> write T Nat
  insert(k) is
    local variable
         ready: Bool := false,
         index: Nat := 0 in
       for i in <.0 .. m-1.> do
          let j = h(k,i) in
             if ~ready /\ T(j) = empty then
                    T := <.if i=j then occupied(k)
                      else T(i) end|i in <.1..len T.>.>;
                    index := j;
                    ready := true
             end
          end
        end;
        index
     end
\end{lstlisting}

m задана в виде константы. Для вызываемой функции $h$ добавлена сигнатура. Предусловие описывает те ситуации, когда исходная процедура не достигнет оператора \textbf{error}. Если известно, что $T(j) \neq$ empty, то можно вызывать функцию elem($T(j)$), чтобы получить значение, хранящееся в $j$'м элементе хеш-таблицы.

Приведем условие, при котором функция выполнит то, что от нее ожидается, т.е. действительно добавит ключ в хэш-таблицу (т.е. при ее выполнении будет достигнут оператор <<\textbf{return} $j$>>):

\begin{lstlisting}
exists i : Nat :- i >= 0 /\ i <= m /\ T(h(k,i)) = empty
\end{lstlisting}


\z Поиск в закрытой хеш-таблице (использовать представление хэш-таблицы из предыдущей задачи), привести условие, при котором функция выполнит то, что от нее ожидается

\begin{codebox}
\Procname{$\proc{Hash-Search}(T,k)$}
\li $i \gets 0$
\li \Repeat $j \gets h(k,i)$
\li \If $T[j] = k$
\li \Then \Return $j$ \End
\li $i \gets i+1$
\li \Until $T[j] = \const{NIL}$ или $i = m$ \End
\li \Error <<отсутствие искомого элемента>>
\end{codebox}


\zhead{Решить задачи\footnote{задачи взяты с сайта http://acm.timus.ru/}}

\z Всё, что от вас требуется — найти сумму всех целых чисел, лежащих между 1 и $N$ включительно.

\z У вас есть несколько камней известного веса $W_1$, ..., $W_n$. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

\z Ваша задача — найти минимальное положительное целое число $Q$ такое, что произведение цифр числа $Q$ в точности равняется $N$.

\z В одном из островных государств Карибского бассейна все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей.

Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается <<за>>, если <<за>> голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается <<против>>. После проведения голосования в группах подсчитывалось количество групп, высказавшихся <<за>> и <<против>>, и вопрос решался положительно в том и только том случае, когда групп, высказавшихся <<за>>, оказывалось более половины общего количества групп.

Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов!
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь трех сторонников в каждой из первых двух групп, и она сможет провести решение всего шестью голосами <<за>>, вместо девяти, необходимых при общем голосовании.

Вам надо написать программу, которая определяет по заданному разбиению избирателей на группы минимальное количество сторонников партии, достаточное, при некотором распределении их по группам, для принятия любого решения. Количество групп нечетно.

\z Рассмотрим последовательность чисел $a_i$, $i$ = 0, 1, 2, ..., удовлетворяющих следующим условиям:
$a_0$ = 0, $a_1$ = 1, $a_{2i} = a_i$, $a_{2i + 1} = a_i + a_i + 1$ для каждого $i$ = 1, 2, 3, ... .

Напишите программу, которая для заданного значения $N$ находит максимальное среди чисел $a_0$, $a_1$, ..., $a_N$.

\z Определение 1. $n$!!...! = $n(n-k)(n-2k)...(n \mod k)$, если $n$ не делится на $k$; $n$!!...! = $n(n-k)(n-2k)...k$, если $n$ делится на $k$ (знаков ! в обоих случаях $k$ штук).

Определение 2. $X \mod Y$ --- остаток от деления $X$ на $Y$. Например, 10 $\mod$ 3 = 1; 3! = 3·2·1; 10!!! = 10·7·4·1.

Мы по заданным $n$ и $k$ смогли вычислить значение выражения из определения 1. А вам слабо?

\z При подготовке задач жюри олимпиады столкнулось со следующей проблемой: нужно было передавать по электронной почте тексты задач. Как известно, электронная почта ненадёжна, сообщения передаются открытым текстом, и существует опасность, что кто-нибудь их перехватит. Членам программного комитета вовсе не хотелось, чтобы задачи стали известны участникам раньше начала соревнования, поэтому они прибегли к методам криптографии. Жюри разработало совершенно новый способ шифрования текста, но он пока не запатентован и поэтому держится в секрете. Впрочем, одну тайну мы вам всё же откроем, новый алгоритм основан на работе с простыми числами и, в частности, использует вычисление $n$-го по счёту простого числа.

Несколько членов программного комитета, независимо друг от друга, разработали программы, производящие такие вычисления, но эти программы выдают разные ответы. Каждый уверен, что он написал свою программу правильно, поэтому жюри встало в тупик и не может продолжать свою работу.

Вы должны помочь жюри и спасти соревнования. Напишите программу, вычисляющую $n$-е по счёту простое число, и, самое главное, она должна работать правильно!

\z Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня, одиноко стоящего на шахматной доске. На всякий случай напомним, что конь ходит буквой <<Г>> --- на две клетки по горизонтали или вертикали в любом направлении, и потом на одну клетку в направлении, перпендикулярном первоначальному.

\z Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000... Всё, что надо --- определить, какая цифра находится в такой последовательности на определённом месте.

\z Пусть задана последовательность из $N$ целых неотрицательных чисел. Медианой такой последовательности в случае нечетного $N$ называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию или убыванию (нетрудно сообразить, что этот элемент имеет номер $\frac{N+1}{2}$ в отсортированной последовательности, если номера считать с единицы). В случае четного $N$ медианой называется среднее арифметическое двух элементов, которые окажутся на местах $\frac{N}{2}$ и $\frac{N}{2}+1$, если последовательность отсортировать. Однако исходная последовательность не обязана быть отсортированной.

Напишите программу, которая по заданной входной последовательности вычисляет ее медиану.
